迷宫寻路三大算法(BFS,DFS,A*)

#迷宫寻路三大算法(BFS,DFS,A*)| 来源: 网络整理| 查看: 265

迷宫寻路

这是我们的数据结构作业本加我们自己再网上找算法记录下来，不过本人比较执着画了几天时间还是把这些算法自己写出来了。总得来说网上所说的大体算法应该就有三种（BFS，DFS，A*）这里是一个验证网址是南阳OJ的一道题这是网址 http://acm.nyis/problem/58 好了不说废话开始吧

BFS

宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。如上所示我要做的就是搜索整张，定义一个二维数组visit， visit[x][y]判断坐标x,y是否被访问，初始化visit为0都没有被访问；定义一个结构体point里面的参数有x,y,dis;其中x,y表示坐标，dis表示出发点到该节点的步数； bfs函数操作： 1，将节点添加到队列里面； 2，从队头取出节点将其访问状态设为1，判断其上下左右四个节点将符合要求的节点添加到队列中； 3，重复1，2操作直到从队列中取出的节点终点返回其dis；具体代码如下

#include #include #include #include #include #include #include #include #include using namespace std; #define MAX 10 int x, y, a, b; struct point { int x, y, dis;//x坐标y坐标步数 }; int fx[4] = { -1,1,0,0 }, fy[4] = { 0,0,-1,1 }; int bfs(int x, int y,int maze[][9]) { queue myque; point tp; tp.x = x;tp.y = y;tp.dis = 0;//初始化开始节点dis设为0 myque.push(tp); while (!myque.empty()) { tp = myque.front();myque.pop();//从队头取节点 if (tp.x == a && tp.y == b) { return tp.dis; }//判断是否到达目的地 for (int i = 0;i < 4;i++) { if (tp.x + fx[i] < 9 && tp.x + fx[i] >= 0 && tp.y + fy[i] < 9 && tp.y + fy[i] >= 0 && maze[tp.x + fx[i]][tp.y + fy[i]] == 0) { point tmp; tmp.x = tp.x + fx[i]; tmp.y = tp.y + fy[i]; tmp.dis = tp.dis + 1; maze[tmp.x][tmp.y] = 1;//添加进队列就将该位置设为1 myque.push(tmp); } } } } int main() { int t; cin >> t; while (t--) { int maze[9][9] = { { 1,1,1,1,1,1,1,1,1 }, { 1,0,0,1,0,0,1,0,1 }, { 1,0,0,1,1,0,0,0,1 }, { 1,0,1,0,1,1,0,1,1 }, { 1,0,0,0,0,1,0,0,1 }, { 1,1,0,1,0,1,0,0,1 }, { 1,1,0,1,0,1,0,0,1 }, { 1,1,0,1,0,0,0,0,1 }, { 1,1,1,1,1,1,1,1,1 }, }; cin >> x >> y >> a >> b; cout =0 && maze[x - 1][y] == 0) //下 { next(x, y, x - 1, y); } if (y + 1 < 9 && maze[x][y + 1] == 0) //左 { next(x, y, x, y+1); } if (y - 1 >=0 && maze[x][y - 1] == 0) //右 { next(x, y, x, y-1); } return 0; } int main() { int t; cin >> t; while (t--) { memset(dis, 1, sizeof(dis));//初始化将dis的值设的比较大 memset(visit, 0, sizeof(visit));//初始化visit将所有值设为0 cin >> x >> y >> a >> b; dis[x][y] = 0; dfs(x, y); cout = 0 && maze[sNode.x + fx[i]][sNode.y + fy[i]] == 0) //判断路径是否可走 { _NODE tp; tp.x = sNode.x + fx[i]; tp.y = sNode.y + fy[i]; tp.f = weight(tp.x, tp.y); //计算节点的权值 tp.dis = sNode.dis + 1; //更新步数 mylist.push_back(tp); } } } return 0; } int main() { int t; cin >> t; while (t--) { int maze[9][9] = { { 1,1,1,1,1,1,1,1,1 }, { 1,0,0,1,0,0,1,0,1 }, { 1,0,0,1,1,0,0,0,1 }, { 1,0,1,0,1,1,0,1,1 }, { 1,0,0,0,0,1,0,0,1 }, { 1,1,0,1,0,1,0,0,1 }, { 1,1,0,1,0,1,0,0,1 }, { 1,1,0,1,0,0,0,0,1 }, { 1,1,1,1,1,1,1,1,1 }, }; cin >> sx >> sy >> ex >> ey; cout

【本文地址】

公司简介

联系我们